import timeit
def Catalan_number(n):
    ans = [1,1]
    for i in range(2,n):
        ans.append(int(ans[-1] * (4*i-2)/(i+1)))
    return ans 

print(timeit.timeit("Catalan_number(10)", "from __main__ import Catalan_number"))

def numTrees(n):
    #初始化一个数组，并将首个元素初始化为1
    s=[0]*(n+1)
    s[0]=1
    #开始循环遍历
    for i in range(1,n+1):
        #为节约内存，首先算出i-1的值
        b=i-1
        #为节约内存，只遍历一半，并将这个结果乘以2即可
        for j in range(i//2):
            s[i]+=s[j]*s[b-j]
        s[i]*=2
        #当i为奇数时，还要将s[i//2]的值加上
        if i%2==1:
            s[i]+=s[i//2]**2
    #返回数组最后一个元素
    return s

print(timeit.timeit("numTrees(10)", "from __main__ import numTrees"))
